package com.faiz.algorithm;

public class Arc {
    public static int solution(int n) {
        int result = 0;
        if (0 == n) {
            return 1;
        }
        for (int i = 0; i < n; i++) {
            //n对点
            result = result + solution(i) * solution(n - 1 - i);
        }
        return result;
    }

    //使用数组来存取中间数据
    public static int solution(int n, int[] array) {
        array[0] = 1;
        array[1] = 1;
        for (int i = 2; i <= n; i++) {
            int result = 0;
            for (int j = 0; j < i; j++) {
                result += array[j]*array[i-j];
            }
            array[i] = result;
        }
        return array[n];
    }
}
